package subject.window;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;

/**
 * 中等题
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 示例 1:
 *
 * 输入: s = "cbaebabacd", p = "abc"
 * 输出: [0,6]
 * 解释:
 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 */
public class findAnagrams {
    public static void main(String[] args) {
        String s = "abab";
        int s_len = s.length();
        String p = "ab";
        int p_len = p.length();
        LinkedList<Integer> list = new LinkedList<>();
        if(s_len < p_len){
            System.out.println("gggggggg");
        }
        int[] sCount = new int[26];
        int[] pCount = new int[26];

        for (int i = 0; i < p_len; i++) {
            int s_index = s.charAt(i) - 'a';
            sCount[s_index] = sCount[s_index] + 1;
            int p_index = p.charAt(i) - 'a';
            pCount[p_index] = pCount[p_index] + 1;
//            ++sCount[s.charAt(i) - 'a'];
//            ++pCount[p.charAt(i) - 'a'];
        }
        if(Arrays.equals(sCount,pCount)){
            list.add(0);
        }

        for (int i = 0; i < s_len - p_len; i++) {
            int s_index_1 = s.charAt(i) - 'a';
            sCount[s_index_1] =  sCount[s_index_1] - 1;
            int s_index_2 = s.charAt(i + p_len) - 'a';
            sCount[s_index_2] = sCount[s_index_2] + 1;

            if(Arrays.equals(sCount,pCount)){
                list.add(i+1);
            }
        }
        System.out.println(list);
    }
}



